Problem

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input: [1,2,3,4] Output: [24,12,8,6]

Note: Please solve it without division and in O(n).

Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

Pre analysis

From the looks of it, this seems like a simple enough problem to solve in linear time and space. We can simply take the product of all the elements in the given array and then, for each of the elements x of the array, we can simply find product of array except self value by dividing the product by x.

Doing this for each of the elements would solve the problem. However, there’s a note in the problem which says that we are not allowed to use division operation. That makes solving this problem a bit harder.

We shall keep Left and right array for each i, and multiple L x R for each i in result